package a12_图论;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 * a06_岛屿数量广搜版
 * </p>
 *
 * @author flyduck
 * @since 2025/3/18
 */
public class a06_岛屿数量广搜版 {
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//
//        int lengthX = scanner.nextInt();
//        int lengthY = scanner.nextInt();
//
//        int[][] grid = new int[lengthX][lengthY];
//        for (int i = 0; i < lengthX; i++) {
//            for (int j = 0; j < lengthY; j++) {
//                grid[i][j] = scanner.nextInt();
//            }
//        }

        int lengthX = 4;
        int lengthY = 5;
        int[][] grid = new int[][]{
                {1,1,0,0,0},
                {1,1,0,0,0},
                {0,0,1,0,0},
                {0,0,0,1,1}
        };

        boolean[][] visited = new boolean[lengthX][lengthY];
        int result = 0;
        for (int i = 0; i < lengthX; i++) {
            for (int j = 0; j < lengthY; j++) {
                if(grid[i][j] == 1 && !visited[i][j]){//必须是没有访问过的岛屿
                    //岛屿+1
                    result++;
                    //标记自己
                    visited[i][j] = true;
                    bfs(grid,visited,i,j);
                }
            }
        }
        System.out.println(result);
    }

    public static final int[][] dirs = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};

    private static void bfs(int[][] grid,
                            boolean[][] visited,
                            int x,
                            int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int[] dir : dirs) {
                int nextX = poll[0] + dir[0];
                int nextY = poll[1] + dir[1];
                if(nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length){
                    if(grid[nextX][nextY] == 1 && !visited[nextX][nextY]){
                        queue.add(new int[]{nextX,nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
}
